perm filename STAIR.TEX[TEX,ALS] blob
sn#581126 filedate 1981-07-07 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00020 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00004 00002 \header{Chapter II.\quad Computing the Controllable Space}
C00009 00003 \parhead{Stage i, i=1,...,k}
C00010 00004 To describe the $i$-th stage we must define some additional notation.
C00014 00005 Then the $i$-th stage proceeds as follows:
C00016 00006 d) We then repartition the matrix into sub-matrices in
C00019 00007 We repeat stage $i$ for $i=1,2,\ldots $ until, say at stage $k$,
C00024 00008 We can give a very easy estimate on the cost in the number of operations required
C00026 00009 \header {Theoretical Proof} \parhead {Theorem 1.} $(Stair)$
C00028 00010 (c) $$(A\zhi (k) )\zhi 2 B\zhi (k) =
C00030 00011 (e) Since $\=A\z 2,1 (k) $ in $(D.5a)$ is zero, and $\=A\z 1,1 (k) $
C00032 00012 We illustrate the algorithm step by step with the following $4$ by $4$ example:
C00036 00013 To further illustrate this method, we give an 11 by 11 example, with randomly
C00039 00014 After the algorithm has been applied, the final system has the form
C00044 00015 \header {Sensitivity Analysis.}
C00048 00016 {\let\spcol=\quad Computing the rank of a sub-block involves computing the singular values
C00051 00017 {\let\spcol=\quad \parhead{Theorem 2.} $(Stair Measure)$
C00059 00018 {\let\spcol=\quad \parhead{Proposition.}
C00064 00019 {\let\spcol=\quad \donothing{We include here another analysis of the Staircase Algorithm.
C00068 00020 {\let\spcol=\quad For the $4$ by $4$
C00069 ENDMK
C⊗;
\header{Chapter II.\quad Computing the Controllable Space}
\append0{\hfill}
\append0{II. Computing the Controllable Space\hfill}
\vskipp
\header{Section II A.\quad Staircase Algorithm}
\append0{\qquad A. Staircase Algorithm\leaddots \count0}
\append0{\qquad\qquad * Description \leaddots \count0}
\vskipp
In this chapter, we describe two methods for computing the controllable
space of a linear system. The first of these is the
Staircase Algorithm.
In this section we describe how the Staircase Algorithm is used in
computing the controllable space of
$$
\eqalgn{
\dot \vx ⊗=A\vx+B\vu;\cr
\vy ⊗=C\vx.\cr
}eqalgn/\eqno (start)
$$
The observable space
can be computed in an analogous
manner by applying this procedure to the transpose
of the system.
This algorithm has appeared in many forms, but the first allusion to it
appeared in [Rosenbrock].
The essential building block used in this method is
the decomposition
$$M=Q \mtxi{R \cr 0 \cr \vdots \cr 0 \cr }mtxi/,\eqno (rank)$$
where $Q$ is orthogonal, and $R$ has full row rank. A very stable method
to compute the rank of $M$ is the Singular Value Decomposition (S.V.D.)
[Golub], [Golub & Reinsch]
$$
M=U
\mtxii{\Sigma\zlo 11 ⊗ 0\cr 0 ⊗ 0\cr}mtxii/
\mtxi{V\zlo 1 \trp \cr V\zlo 2 \trp \cr}mtxi/.
$$
We can then obtain $(rank)$ by setting $Q=U$ and $R=\Sigma\zlo 11 V\zlo 1 \trp$.
One can compute this decomposition with fewer operations,
and almost as reliably, using the
QR-Decomposition with Pivoting [LINPACK], which gives rise to the
QRE Decomposition in which a matrix $M$ is decomposed as
$$
M = Q R E
$$
where $Q$ is an orthogonal matrix, $E$ is a permutation matrix, and
$R$ is upper triangular with the property that
$$
\abs{r\zlo ii }≥ \abs{r\zlo jk } \quad \hbox{ for all } i,j,k,\; i≤j,i≤k
$$
[LINPACK].
An $R$ with this property is said to be {\it graded}.
We then obtain $(rank)$ by using the same $Q$ from this decomposition
and setting the $R$ in $(rank)$ to be the $RE$ from this decomposition.
In the current implementation, the QRE Decomposition is used.
A note on notation: In this section I will use the notation FRR to
mean Full Row Rank, FCR to mean Full Column Rank, and I will put
iteration numbers as superscripts.
The Staircase Algorithm
consists of a series of similarity transformations to the system
$\dot\vx = A \vx + B \vu$ as follows:
\noindent{\bf Stage 0.}
Let $$T↑{(0) -1} \mtxi{B↓1 \cr 0 \cr \vdots \cr 0 \cr }mtxi/$$
be the QR-decomposition of $B$, where
$B↓1$ is of full row rank, and $T↑{(0)}$ is orthogonal.
We then apply the transformation as follows:
$$
\eqalgn{
A↑{(1)} ⊗= T↑{(0)} A T↑{(0) \tp}
\cr \vtskipp
B↑{(1)} ⊗= T↑{(0)} B = \mtxi{B↓1 \cr 0 \cr \vdots \cr 0 \cr }mtxi/
\cr \vtskipp
C↑{(1)} ⊗= C T↑{(0) \tp},
\cr
}eqalgn/ \eqno (D.1)
$$
The part $B↑{(1)}$ will be unchanged in subsequent stages.
\parhead{Stage i, i=1,...,k}
At each subsequent stage $(i)$ we compute an orthogonal $T↑{(i)}$
and apply it to $A↑{(i)}$, $B↑{(i)}$, $C↑{(i)}$,
as in $(D.1)$, to obtain $A↑{(i+1)}$,
$B↑{(i+1)}$, $C↑{(i+1)}$ so that
$$
\eqalgn{
A↑{(i+1)} ⊗= T↑{(i)} A↑{(i)} T↑{(i) \tp}
\cr \vtskipp
B↑{(i+1)} ⊗= T↑{(i)} B↑{(i)} = B↑{(1)}
\cr \vtskipp
C↑{(i+1)} ⊗= C↑{(i)} T↑{(i) \tp}.
\cr
}eqalgn/ \eqno (D.2)
$$
To describe the $i$-th stage we must define some additional notation.
(I recommend you read what follows first with $i=1$ in your mind, noting
that in this case the entire upper left part in $(D.3a)$ will be empty!)
At the $i$-th stage we have
(The superscripts give the number of the last
stage in which each block was changed.)
$$
\eqalgn{
A\zhi (i) ⊗
=\mtxx{
\; A\z 1,1 (1) \; ⊗ \; A\z 1,2 (2) \; ⊗ \; A\z 1,3 (3) \; ⊗ \;
\cdots ⊗ A\z 1,i-2 (i-1) ⊗ A\z 1,i-1 (i-1) ⊗
\vtrule ⊗ A\z 1,i (i) ⊗ \vtrule ⊗
\cr \vtjoin
\; A\z 2,1 (2) \; ⊗ \; A\z 2,2 (2) \; ⊗ \; A\z 2,3 (3) \; ⊗ \;
\cdots ⊗ A\z 2,i-2 (i-1) ⊗ A\z 2,i-1 (i-1) ⊗
\vtrule ⊗ A\z 2,i (i) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ A\z 3,2 (3) ⊗ A\z 3,3 (3) ⊗
\cdots ⊗ A\z 3,i-2 (i-1) ⊗ A\z 3,i-1 (i-1) ⊗
\vtrule ⊗ A\z 3,i (i) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ 0 ⊗ ⊗ ⊗ \vdots ⊗ \vdots ⊗ \vtrule ⊗ \vdots ⊗ \vtrule ⊗ \; X \;
\cr \vtjoin
⊗ ⊗ ⊗
⊗ A\z i-2,i-2 (i-1) ⊗ A\z i-2,i-1 (i-1) ⊗
\vtrule ⊗ A\z i-2,i (i) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ ⊗ ⊗
⊗ A\z i-1,i-2 (i-1) ⊗ A\z i-1,i-1 (i-1) ⊗
\vtrule ⊗ A\z i-1,i (i) ⊗ \vtrule ⊗
\cr
\hzrule
⊗ 0 ⊗ ⊗
\cdots ⊗ 0 ⊗ A\z i,i-1 (i-1) ⊗
\vtrule ⊗ A\z i,i (i) ⊗ \vtrule ⊗ X
\cr
\hzrule
⊗ ⊗ ⊗
⊗ ⊗ 0 ⊗
\vtrule ⊗ A\z i+1,i (i) ⊗ \vtrule ⊗ X
\cr \vtjoin
⊗ 0 ⊗ ⊗
\cdots ⊗ 0 ⊗ ⊗
\vtrule ⊗ X ⊗ \vtrule ⊗ X
\cr
}mtxx/
\cr
}eqalgn/
\eqno {(D.3a)}
$$
We write the above partition, grouped by the lines, as
$$
\eqalgn{
A\zhi (i) ⊗=
\mtxiii{
F\z 1,1 (i) ⊗ F\z 1,2 (i) ⊗ F\z 1,3 (i) \cr \vtskip
F\z 2,1 (i) ⊗ F\z 2,2 (i) ⊗ F\z 2,3 (i) \cr \vtskip
F\z 3,1 (i) ⊗ F\z 3,2 (i) ⊗ F\z 3,3 (i) \cr
}mtxiii/
\cr
}eqalgn/
\eqno {(D.3b)}
$$
where
\lm \qquad\qquad $F\z 1,1 (i) $ is square of size $r\zlo 1 + \ldotss + r\zlo i-1 $,
\vvskipp
\lm \qquad\qquad $F\z 2,2 (i) = A\z ii (i) $ is of size $r\zlo i $ by $r\zlo i $,
\vvskipp
\lm \qquad\qquad $A\zhi (i) $ (the entire matrix) is $n$ by $n$,
\vvskipp
\lm \qquad\qquad $F\z 2,1 (i) $ and $F\z 3,2 (i) $
have rank $r\zlo i $ and $r\zlo i+1 $ respectively,
\vvskipp
\lm \qquad\qquad and the other blocks have dimensions to match.
\noindent At stage $i=1, F\z 1,1 (1) $ is empty, so we have
$$
A\zhi (1) =
\mtxii{F\z 2,2 (1) ⊗ F\z 2,3 (1) \cr \vtskip
F\z 3,2 (1) ⊗ F\z 3,3 (1) \cr }mtxii/
=
\mtxii{A\z 1,1 (1) ⊗ X \cr \vtskip X ⊗ X \cr }mtxii/
$$
Then the $i$-th stage proceeds as follows:
a) Decompose
$$
Q\trp \mtxi{R \cr 0 \cr \vdots \cr 0 \cr }mtxi/ = F\z 3,2 (i)
\eqno (stage.a)
$$
with $Q$ orthogonal, $R$ with full row rank $r\zlo i+1 $ using some scheme based
on, for example,
the QRE Decomposition.
b) Let
$$
T\zhi (i) =
\mtxiii{I ⊗ 0 ⊗ 0 \cr 0 ⊗ I ⊗ 0 \cr 0 ⊗ 0 ⊗ Q \cr}mtxiii/
\eqno (stage.b)
$$
with blocks matching those in $(D.3b)$
\vvskipp
c) Then
$$
\eqalgn{
A\zhi (i+1)
⊗=
T\zhi (i) A\zhi (i) (T\zhi (i) )\trp
\cr \vtskipp
⊗=
\mtxiii{
F\z 1,1 (i) ⊗ F\z 1,2 (i) ⊗ F\z 1,3 (i) Q\trp \cr \vtskip
F\z 2,1 (i) ⊗ F\z 2,2 (i) ⊗ F\z 2,3 (i) Q\trp \cr \vtskip
Q F\z 3,1 (i) ⊗ Q F\z 3,2 (i) ⊗ Q F\z 3,3 (i) Q\trp \cr
}mtxiii/
\cr \vtskipp
⊗=
\mtxiii{
\=F\z 1,1 (i) ⊗ \=F\z 1,2 (i) ⊗ \=F\z 1,3 (i) \cr \vtskip
\=F\z 2,1 (i) ⊗ \=F\z 2,2 (i) ⊗ \=F\z 2,3 (i) \cr \vtskip
0 ⊗ \mtxi{R \cr 0 \cr \vdots \cr 0 \cr }mtxi/ ⊗ \=F\z 3,3 (i) \cr
}mtxiii/
\cr
}eqalgn/
\eqno (stage.c)
$$
where $ F\z 1,1 (i) = \=F\z 1,1 (i) $.
d) We then repartition the matrix into sub-matrices in
preparation for the next stage $(i+1)$, so that the result of the
$i$-th stage $(stage.c)$ is rewritten
$$
A\zhi (i+1)
=
\mtxiii{
F\z 1,1 (i+1) ⊗ F\z 1,2 (i+1) ⊗ F\z 1,3 (i+1) \cr \vtskip
F\z 2,1 (i+1) ⊗ F\z 2,2 (i+1) ⊗ F\z 2,3 (i+1) \cr \vtskip
F\z 3,1 (i+1) ⊗ F\z 3,2 (i+1) ⊗ F\z 3,3 (i+1) \cr
}mtxiii/
\eqno (stage.d)
$$
where
$$
\eqalgn{
F\z 1,1 (i+1)
⊗=
\mtxii{
\=F\z 1,1 (i) ⊗ \=F\z 1,2 (i) \cr \vtskip
\=F\z 2,1 (i) ⊗ \=F\z 2,2 (i) \cr
}mtxii/\;
\hbox{ square of size $r\zlo 1 + \ldots + r\zlo i $}
\cr \vtskipp
F\z 2,1 (i+1)
⊗=
\mtxiv{0 ⊗ \cdotss ⊗ 0 ⊗ R \cr }mtxiv/
\cr \vtskipp
F\z 2,2 (i+1)
⊗=
A\z i+1,i+1 (i+1) \quad \hbox{from $(D.3a)$}
\quad (r\zlo i+1 \hbox{ by } r\zlo i+1 )
\cr
⊗
\hbox{(part of subblock $\=F\z 33 (i) $)}
\cr \vtskipp
\mtxii{F\z 1,2 (i+1) ⊗ F\z 1,3 (i+1) \cr}mtxii/
⊗=
\mtxi{\=F\z 1,3 (i) \cr \vtskip \=F\z 2,3 (i) \cr}mtxi/
\cr \vtskipp
\mtxii{F\z 2,2 (i+1) ⊗ F\z 2,3 (i+1) \cr \vtskip
F\z 3,2 (i+1) ⊗ F\z 3,3 (i+1) \cr}mtxii/
⊗=
\=F\z 3,3 (i)
\cr
}eqalgn/
$$
We are now ready to do the $(i+1)$-th stage. Observe that the block
denoted at the $i$-th stage by $F\z 1,1 (i) $ is not changed at the $i$-th stage,
or at subsequent stages.
We repeat stage $i$ for $i=1,2,\ldots $ until, say at stage $k$,
the block $F\z 3,2 (k) $ has rank zero, either because it has all zero entries,
or because it is an empty block (e.g. has zero rows, in which case,
the whole system is entirely controllable.) Thus at the
final stage $(k)$, the matrix can be written as
$$
A\zhi (k) =
\mtxiii{
F\z 1,1 (k) ⊗ F\z 1,2 (k) ⊗ F\z 1,3 (k) \cr \vtskip
F\z 2,1 (k) ⊗ F\z 2,2 (k) ⊗ F\z 2,3 (k) \cr \vtskip
0 ⊗ 0 ⊗ F\z 3,3 (k) \cr
}mtxiii/.
\eqno {(D.4a)}
$$
We can group together the 1,3 and 2,3 blocks to get
$$
A\zhi (k) =
\mtxii{
\mtxii{
\=F\z 1,1 (k) ⊗ \=F\z 1,2 (k) \cr \vtskip
\=F\z 2,1 (k) ⊗ \=F\z 2,2 (k) \cr
}mtxii/
⊗ \=A\z 1,2 (k)
\cr \vtskip
0 ⊗ \=A\z 2,2 (k)
\cr
}mtxii/.
\eqno {(D.4b)}
$$
We may expand $(D.4b)$ to obtain the matrix $(D.5a)$ where the
bars mark the partition in $(D.4b)$:
$$
\eqalgn{
A\zhi (k) ⊗= \cr
⊗\mtxix{
\; A\z 1,1 (1) \; ⊗ \; A\z 1,2 (2) \; ⊗ \; A\z 1,3 (3) \; ⊗ \;
\cdots ⊗ A\z 1,k-2 (k-1) ⊗ A\z 1,k-1 (k-1) ⊗
A\z 1,k (k) ⊗ \vtrule ⊗
\cr \vtjoin
A\z 2,1 (2) ⊗ A\z 2,2 (2) ⊗ A\z 2,3 (3) ⊗
\cdots ⊗ A\z 2,k-2 (k-1) ⊗ A\z 2,k-1 (k-1) ⊗
A\z 2,k (k) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ A\z 3,2 (3) ⊗ A\z 3,3 (3) ⊗
\cdots ⊗ A\z 3,k-2 (k-1) ⊗ A\z 3,k-1 (k-1) ⊗
A\z 3,k (k) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ 0 ⊗ ⊗ ⊗ \vdots ⊗ \vdots ⊗ \vdots ⊗ \vtrule ⊗ \; \=A\z 1,2 (k) \;
\cr \vtjoin
⊗ ⊗ ⊗
⊗ A\z k-2,k-2 (k-1) ⊗ A\z k-2,k-1 (k-1) ⊗
A\z k-2,k (k) ⊗ \vtrule ⊗
\cr \vtjoin
⊗ ⊗ ⊗
⊗ A\z k-1,k-2 (k-1) ⊗ A\z k-1,k-1 (k-1) ⊗
A\z k-1,k (k) ⊗ \vtrule ⊗
\cr
\hzrule
⊗ ⊗ 0 ⊗
= ⊗ \=A\z 2,1 (k) ⊗ ⊗
⊗ \vtrule ⊗ \=A\z 2,2 (k)
\cr
}mtxix/
\cr
}eqalgn/
\eqno (D.5a)
$$
where
$$
\eqalgn{
⊗A\z 2,1 (2) ,\ldotss,A\z k-1,k-2 (k-1) \hbox{ all have full row rank }
r\zlo 2 ,\ldotss,r\zlo k-1 \hbox{ respectively,}
\cr \vtskipp
⊗A\z 1,1 (1) ,\ldotss,A\z k-1,k-1 (k-1) \hbox{ are of size }
r\zlo 1 \hbox{ by }r\zlo 1 ,\ldotss,r\zlo k-1
\hbox{ by }r\zlo k-1 \hbox{ respectively,}
\cr \vtskipp
⊗\=A\z 2,1 (k) = 0,\=A\z 2,2 (k) ,\=A\z 1,2 (k)
\hbox{ may all be empty, if entirely controllable,}
\cr \vtskipp
⊗r\zlo 1 ≥ r\zlo 2 ≥ \ldotss ≥ r\zlo k-1 .
\cr
}eqalgn/
\eqno {(D.5b)}
$$
(The superscripts give the number of the last
stage in which each block was changed.)
\lm We also have
$$
B\zhi (k) =
\mtxi{B\zlo 1 \cr 0 \cr \vdots \cr 0 \cr}mtxi/
= B\zhi (1)
\eqno{(D.5c)}
$$
We can give a very easy estimate on the cost in the number of operations required
by considering that the number of multiplications or
additions/subtractions is approximately equal to the number of matrix elements
annihilated. But that is no more than for the QR decomposition,
so we can bound the cost simply by the
the cost of doing a QR decomposition on $A$.
That cost is approximately
${4\over 3}n\zhi 3 + O(n)$.
Since the decomposition stops when the controllable part
has been computed, after
$n\zlo c $ steps,
the
cost of a staircase sweep becomes approximately
$$
\hbox{cost }\quad\approx\quad {4\over 3}n\zhi 3 - {4\over 3}n\z \=c 3 + O(n),
$$
where $n\zlo \=c = n - n\zlo c $
is the size of the uncontrollable part.
\newpage
\header {Theoretical Proof} \parhead {Theorem 1.} $(Stair)$
\append0{\qquad\qquad * Theoretical Proof \leaddots \count0}
\thbody{Given $A\zhi (k) $ and $B\zhi (k) $ as in $(D.5)$,
then we have a controllability
decomposition of $\dot\vx = A \vx + B \vu$. }thbody/
\parhead Proof.
Observe that
(a) $\mthop colsp (B\zhi (k) ) =
\mthop span \mtxiii{e\zlo 1 ⊗ \ldotss ⊗ e\zlo {r\zlo 1 } \cr}mtxiii/$,
\vvskipp
(b) $$A\zhi (k) B\zhi (k) =
\mtxi{X \cr A\z 2,1 (2) B\zlo 1 \cr 0 \cr \vdots \cr 0 \cr}mtxi/.$$
\vvskipp
Since $A\z 2,1 (2) $ has full row rank $r\zlo 2 $ and $B\zlo 1 $ has full
row rank $r\zlo 1 ≥ r\zlo 2 $,
it follows $A\z 2,1 (2) B\zlo 1 $ has full row rank $r\zlo 2 $ and
$$
\mthop rank \mtxii{B\zlo 1 ⊗ X \cr 0 ⊗ A\z 2,1 (2) B\zlo 1 \cr
0 ⊗ 0 \cr \vdots ⊗ \vdots \cr 0 ⊗ 0 \cr }mtxii/
= \mthop rank \mtxiii{B\zhi (k) ⊗ ⊗ A\zhi (k) B\zhi (k) \cr}mtxiii/
= r\zlo 1 + r\zlo 2,
$$
(c) $$(A\zhi (k) )\zhi 2 B\zhi (k) =
\mtxi{X \cr X \cr A\zlo 3,2 (A\zlo 2,1 B\zlo 1 ) \cr 0 \cr
\vdots \cr 0 \cr}mtxi/$$
(the $\zhi (k) $ superscripts are omitted),
where, as in (b), $A\zlo 3,2 (A\zlo 2,1 B\zlo 1 )$ has full row rank $r\zlo 3 $ .
Therefore,
$$
\mthop rank
\mtxiii{B\zlo 1 ⊗ X ⊗ X \cr 0 ⊗ A\zlo 2,1 B\zlo 1 ⊗ X \cr
0 ⊗ 0 ⊗ A\zlo 3,2 (A\zlo 2,1 B\zlo 1 ) \cr
0 ⊗ 0 ⊗ 0 \cr \vdots ⊗ \vdots ⊗ \vdots \cr 0 ⊗ 0 ⊗ 0 \cr
}mtxiii/
=
\mthop rank \mtxiii{B ⊗ A B ⊗ A\zhi 2 B \cr}mtxiii/
=
r\zlo 1 + r\zlo 2 + r\zlo 3.
$$
(d) Continuing in this way, we see that
$$
\eqalgn{
\mthop rank ⊗
\mtxiv{B\zhi (k) ⊗ A\zhi (k) B\zhi (k) ⊗ \cdotss ⊗
(A\zhi (k) )\zhi k-1 B\zhi (k) \cr }mtxiv/
\cr
⊗= \mthop rank
\mtxiv{B ⊗ A B ⊗ \cdotss ⊗
A\zhi k-1 B \cr }mtxiv/
\cr
⊗= r\zlo 1 + r\zlo 2 + \ldotss + r\zlo k
\cr
}eqalgn/
$$
(e) Since $\=A\z 2,1 (k) $ in $(D.5a)$ is zero, and $\=A\z 1,1 (k) $
(the upper left block) has
$r\zlo 1 + r\zlo 2 + \ldotss + r\zlo k $ rows, and $B\zhi (k) $
has the form in $(D.5c)$, only the
first $r\zlo 1 + \ldotss + r\zlo k $ rows of $(A\zhi (k) )\zhi k B\zhi (k) $
will be nonzero, and
indeed this will be true also for all higher powers of $A\zhi (k) $. Hence
$$
\eqalgn{
\mthop rank ⊗
\mtxiv{B ⊗ A B ⊗ \cdotss ⊗
A\zhi n-1 B \cr }mtxiv/
\cr
⊗= \mthop rank
\mtxiv{B\zhi (k) ⊗ A\zhi (k) B\zhi (k) ⊗ \cdotss ⊗
(A\zhi (k) )\zhi n-1 B\zhi (k) \cr }mtxiv/
\cr
⊗= r\zlo 1 + r\zlo 2 + \ldotss + r\zlo k
\cr
}eqalgn/
$$
where $n$ is the size of the original matrix $A$.
By the Cayley Hamilton Theorem, we need not go any further
than $n-1$.
\QED
\newpage
We illustrate the algorithm step by step with the following $4$ by $4$ example:
$$
\eqalgn{
\dot\vx ⊗=
\mtxiv{
-{1\over 2} ⊗ \quad 0 ⊗ \quad {5\over 2} ⊗ \quad 0 \cr \vtskip
-\sqrt{2} ⊗ \quad -1 ⊗ \quad {8\over \sqrt{2}} ⊗ \quad 0 \cr \vtskip
-{3\over 2} ⊗ \quad 0 ⊗ \quad {7\over 2} ⊗ \quad 0 \cr \vtskip
{1\over \sqrt{2}} ⊗ \quad -1 ⊗ \quad {3\over \sqrt{2}} ⊗ \quad -2 \cr
}mtxiv/
\vx +
\mtxi{0 \cr \vtskip 1 \cr \vtskip 0 \cr \vtskip 1 \cr}mtxi/ \vu .
\cr
}eqalgn/\eqno (sample)
$$
After stage 0., the $B$ matrix has been collapsed to a part of full row rank plus
zeroes, giving the result
$$
\eqalgn{
\dot\vx\zhi (0) ⊗=
\rmtxiv{
-2.000 ⊗ -0.354 ⊗ -5.500 ⊗ -0.354 \cr \vtskip
-0.707 ⊗ \ 0\ ⊗ \ 0\ ⊗ 1.000 \cr \vtskip
\ 0\ ⊗ 1.061 ⊗ 3.500 ⊗ 1.061 \cr \vtskip
0.707 ⊗ -0.500 ⊗ -3.536 ⊗ -1.500 \cr
}rmtxiv/
\vx\zhi (0) +
\rmtxi{-1.414 \cr \vtskip 0 \cr \vtskip 0 \cr \vtskip 0 \cr}rmtxi/ \vu .
\cr
}eqalgn/\eqno (sample.s0)
$$
After stage 1 of the reduction ($C/\=C$ split) of the matrix $A$ we have
$$
\eqalgn{
\dot\vx\zhi (1) ⊗=
\rmtxiv{
-2.000 ⊗ \ 0\ ⊗ -5.500 ⊗ -0.500 \cr\vtskip
1.000 ⊗ -1.000 ⊗ -2.500 ⊗ -1.500 \cr\vtskip
\ 0\ ⊗ ↑*0\ ⊗ 3.500 ⊗ 1.500 \cr\vtskip
\ 0\ ⊗ ↑*0\ ⊗ -2.500 ⊗ -0.500 \cr
}rmtxiv/
\vx\zhi (1) +
\rmtxi{-1.414 \cr \vtskip 0 \cr \vtskip 0 \cr \vtskip 0 \cr}rmtxi/ \vu .
\cr
}eqalgn/\eqno (sample.s1)
$$
The *-ed entries are all zero, so that this is all there is to this reduction.
In practice, in noting the zeroes, the method goes through an extra
iteration,
resulting in a change to this last result:
$$
\eqalgn{
\dot\vx\zhi (2) ⊗=
\rmtxv{
-2.000 ⊗ \ 0\ ⊗ \vtrule ⊗ 4.075 ⊗ -3.727 \cr \vtjoin
1.000 ⊗ -1.000 ⊗ \vtrule ⊗ 1.082 ⊗ -2.707 \cr \hzrule
\ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ 2.516 ⊗ -3.793 \cr \vtjoin
\ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ .206 ⊗ .484 \cr
}rmtxv/
\vx\zhi (2) +
\rmtxi{-1.414 \cr \vtskipp \ 0\ \cr \hzruleskip \vtskip
\ 0\ \cr \vtskipp \ 0\ \cr}rmtxi/ \vu .
\cr
}eqalgn/\eqno (sample.s2)
$$
It is this last result which is used in subsequent computations.
\newpage
To further illustrate this method, we give an 11 by 11 example, with randomly
chosen eigenvalues. For the original matrix $A$ in the system $(start)$,
we use
{
\let\rspcol=\
\mathrm dff \mathit jll \mathsy xzz
$$
\left(\pass\rbxiv{
-0.292 0.518 0.263 0.906
-0.148 0.308 0.859 0.341
0.807 0.705 0.730 0.640
0.141 1.305 -0.153 1.208
-0.048 0.896 0.035 0.474
1.183 0.422 0.232 0.328
1.118 1.188 0.083 1.053
0.598 0.025 0.121 0.249
-0.161 0.247 0.546 0.475
1.351 -0.237 0.993 -0.138
0.850 -0.182 1.164 0.127
}rbxiv/\endpass
\rspcol
\pass\rbxiv{
-0.143 0.189 0.467 1.598
0.970 0.552 -0.016 1.216
0.269 0.615 0.830 -0.366
-0.778 -0.499 1.392 0.109
-0.309 0.178 1.210 0.199
0.933 0.093 0.496 -0.389
-0.059 0.390 1.562 -0.272
0.376 0.113 -0.064 0.646
0.487 0.154 0.127 1.416
0.718 1.557 -0.257 0.577
1.543 0.460 -0.152 1.133
}rbxiv/\endpass
\rspcol
\pass\rbxiii{
0.905 0.530 0.076
0.957 0.770 -0.093
0.624 0.313 1.009
0.176 0.649 0.510
0.770 0.448 0.395
-0.403 1.410 0.591
0.474 0.477 0.940
0.149 0.220 0.257
0.781 0.585 0.086
0.731 0.183 0.122
0.410 0.791 0.638
}rbxiii/\endpass\right).
\eqno (eleven.a)
$$
The starting values for the input vectors are
$$
\pass\rmtxiv{
0.558 0.995 -1.433 -0.075
-0.964 0.501 -2.963 0.739
1.022 -0.367 2.727 -0.069
2.551 0.063 1.243 -0.422
0.831 0.491 1.115 0.041
-0.270 -0.957 0.206 -0.011
2.722 -0.637 3.297 -0.593
-0.140 -0.461 0.836 -0.047
-0.328 0.584 -2.275 0.254
-1.208 -0.135 0.011 0.152
-0.893 -0.185 -2.903 0.089
}rmtxiv/\endpass .
\eqno (eleven.b)
$$
\pagebreak
}
After the algorithm has been applied, the final system has the form
{
\let\rspcol=\
\mathrm dff \mathit jll \mathsy xzz
{\let\rspcol=\,
$$
\left(\rbxvi{\cr
-0.762 ⊗ 1.799 ⊗ -0.798 ⊗ 0.261 ⊗ \vtrule \cr\vtjoin
-0.013 ⊗ 1.596 ⊗ -1.097 ⊗ -1.184 ⊗ \vtrule \cr\vtjoin
0.022 ⊗ -0.487 ⊗ -0.761 ⊗ -0.129 ⊗ \vtrule \cr\vtjoin
-0.006 ⊗ -0.663 ⊗ 0.290 ⊗ 1.109 ⊗ \vtrule \cr\vtjoin\hzrule
-0.008 ⊗ -1.325 ⊗ 0.645 ⊗ 1.224 ⊗ \vtrule \cr\vtjoin
-0.024 ⊗ \ 0\ ⊗ 0.089 ⊗ 0.067 ⊗ \vtrule \cr\vtjoin
-0.039 ⊗ \ 0\ ⊗ \ 0\ ⊗ 0.057 ⊗ \vtrule \cr\vtjoin\hzrule
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule \cr \cr
}rbxvi/\rbxviii{\cr
0.457 ⊗ -1.362 ⊗ -0.509 ⊗ \vtrule ⊗ 1.038 ⊗
1.394 ⊗ 0.978 ⊗ 0.617 \cr\vtjoin
-0.792 ⊗ -2.069 ⊗ 0.339 ⊗ \vtrule ⊗ -0.350 ⊗
0.074 ⊗ -1.305 ⊗ -0.589 \cr\vtjoin
1.887 ⊗ -0.230 ⊗ -0.280 ⊗ \vtrule ⊗ 0.071 ⊗
-0.612 ⊗ -0.429 ⊗ -1.160 \cr\vtjoin
1.579 ⊗ 0.063 ⊗ -0.206 ⊗ \vtrule ⊗ -0.135 ⊗
0.054 ⊗ 0.142 ⊗ 0.385 \cr\vtjoin\hzrule
3.612 ⊗ -0.988 ⊗ 0.384 ⊗ \vtrule ⊗ 0.545 ⊗
0.120 ⊗ 0.791 ⊗ 0.628 \cr\vtjoin
0.029 ⊗ -1.201 ⊗ 0.527 ⊗ \vtrule ⊗ 0.166 ⊗
0.349 ⊗ -0.223 ⊗ 0.314 \cr\vtjoin
0.126 ⊗ -0.304 ⊗ -0.240 ⊗ \vtrule ⊗ 0.321 ⊗
0.360 ⊗ 0.179 ⊗ 0.087 \cr\vtjoin\hzrule
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ 0.517 ⊗
0.229 ⊗ 0.026 ⊗ 0.025 \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ 0.084 ⊗
0.636 ⊗ 0.007 ⊗ -0.136 \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ 0.269 ⊗
\ 0\ ⊗ \ 0\ ⊗ 0.276 \cr\vtjoin
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \vtrule ⊗ 0.266 ⊗
-0.124 ⊗ 0.165 ⊗ 0.162 \cr \cr
}rbxviii/\right).
$$
}
The input vectors {\sl B}, in their final reduced form, are
$$
\rmtxiv{\cr
3.097 ⊗ -0.994 ⊗ 6.802 ⊗ -0.821 \cr\vtskip
3.123 ⊗ 0.663 ⊗ \ 0\ ⊗ -0.409 \cr\vtskip
\ 0\ ⊗ 1.456 ⊗ \ 0\ ⊗ 0.200 \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ -0.553 \cr \hzruleskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr \hzruleskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr\vtskip
\ 0\ ⊗ \ 0\ ⊗ \ 0\ ⊗ \ 0\ \cr \cr
}rmtxiv/.
$$
}
\newpage
\header {Sensitivity Analysis.}
\append0{\qquad\qquad * Sensitivity Analysis \leaddots \count0}
The Staircase Algorithm can give a rough estimate of the sensitivity
of the results to small perturbations in the original data. Since the
algorithm uses only orthogonal transformations, the resulting system $(D.5)$ will
be similar to a system that differs from the original system $(start)$ by only
a small multiple of the machine precision [Wilkinson], as long as the ranks
of the subdiagonal blocks are computed correctly.
If the ranks are not computed correctly, then the partitions will fall in the
wrong place, and the computed values for the dimension of the controllable space
will be off.
Once a rank error is made in a block, it is propagated throughout the
remaining stages.
Given any system, a small random perturbation will most likely cause the
system to become completely controllable.
After we have reduced the system by the Staircase Algorithm, the
controllability matrix looks like
$$
\mtxiii{B ⊗ A B ⊗ A\zhi 2 B \cr}mtxiii/
=
\mtxiii{B\zlo 1 ⊗ X ⊗ X \cr 0 ⊗ A\zlo 2,1 B\zlo 1 ⊗ X \cr
0 ⊗ 0 ⊗ A\zlo 3,2 (A\zlo 2,1 B\zlo 1 ) \cr
0 ⊗ 0 ⊗ 0 \cr \vdots ⊗ \vdots ⊗ \vdots \cr 0 ⊗ 0 ⊗ 0 \cr
}mtxiii/
$$
where only the first $r$ rows are nonzero, $r$ being the dimension of
the controllable space
$\Sscr\zlo c $.
A small perturbation to either $A$ or $B$ will
introduce nonzeroes below row $r$, signifying a controllable space
of larger dimension. Our problem is to decide what remains controllable
through all such small perturbations, or equivalently find the smallest
$\Sscr\zlo c $
we can obtain over all such perturbations.
Specifically, if we allow perturbations up to size \var{TOL}, we would
like to determine what is the smallest
$\Sscr\zlo c $
we can find within such a tolerance \var{TOL}.
These comments
apply not only to the Staircase Algorithm, but also to any other
method used to compute the controllable space, including the one
given in the next section.
{\let\spcol=\quad Computing the rank of a sub-block involves computing the singular values
of that block.
If we decide that all the singular values below a certain value
$\var{TOL}≡\sigma\zlo r+1 $ are $0$, where $r$ is the computed rank,
then we have essentially perturbed
the matrix system by the amount \var{TOL}. These perturbations will
depend on the tolerance implied in the input data, and, in general, they will
be much greater than the machine precision.
The relevant measure of sensitivity to perturbations
would thus appear to be based on the collection of the smallest singular
values for each sub-block.
However, these individual
values are not good indications of bad conditioning,
as is
shown in the following example:
$$
\dot\vx =
\mtxii{0 ⊗ 0 \cr \sqrt{\epsilon} ⊗ 1 \cr}mtxii/
\vx
+
\mtxi{\sqrt{\epsilon} \cr b\zlo 2 \cr}mtxi/
\vu,
$$
where $b\zlo 2 =0$.
The only singular value for each
subdiagonal block (we must include the block $b\zlo 1 $ from stage 0.)
is large (on the order of $\sqrt\epsilon$),
so it appears the controllable space has dimension
$2$. But if we set $\s b\zlo 2 = -\epsilon$, a perturbation of size $\epsilon$,
then $\s {\vec b }$ becomes an eigenvector of $A$, and the controllable
space is reduced to dimension $1$.
However, the {\it product} of these small singular values
is a more reliable
measure, meaning that if the product is large then there is no perturbation
that will give rise to a different answer.
In the multiple input case this is just an empirical observation, but
for the single input case, we can actually prove the following theorem:
}
{\let\spcol=\quad \parhead{Theorem 2.} $(Stair Measure)$
\thbody{Consider the system
$$
\dot\vx = A \vx + B \vu.\eqno (system)
$$
Suppose $B$ consists of one column, and that the system is in the Staircase
form, which in this case is equivalent to saying that $B=b\zlo 1 \vec e \zlo 1 $
and $A$ upper Hessenberg, where
$\vec e \zlo 1 = \mtxiv{1⊗0⊗\ldots⊗0\cr}mtxiv/\trp$.
Suppose further that $$\norm{A}\zlo 2 + \norm{B}\zlo 2 ≤ {{1\over 4}}$$ and that
the product of the subdiagonal elements satisfy
$$
\abs{b\zlo 1 a\zlo 2,1 \ldotss a\zlo n,n-1 } ≡ \mu\zlo s > {\epsilon \over 4}
$$
with $\epsilon < {1\over 4}$.
\parhead{Then } the system $(system)$ is completely controllable within
any $\epsilon $ perturbation -- i.e. if the matrices $A$ and $B$ are subjected
to {\it any} $\epsilon $ perturbation, the system remains controllable.
}thbody/
\parhead{Proof:}
Let
$$F(\lambda) = \mtxii{B ⊗ \lambda I - A\cr}mtxii/.$$
If the system were almost uncontrollable, then $F(\lambda\zlo i )$ would have
to be almost row-rank deficient, for $\lambda\zlo i $ an eigenvalue of $A$.
So we need only look at $\lambda = \lambda\zlo i $.
For any such $\lambda\zlo i $, $\abs{\lambda\zlo i } ≤ \norm{A}\zlo 2 ≤ {1\over 4}$.
If $A$ is perturbed by $\epsilon $, then its eigenvalues will still satisfy
$$
\abs{\lambda } ≤ \norm{A+\epsilon E}\zlo 2 \!
≤ {1\over 4}+\epsilon , \eqno(\lambda bound)$$
where $\norm{E} ≤ 1$.
We will
prove that $F(\lambda )$ has full row-rank for all $\lambda $ satisfying this
last condition.
Augment $F(\lambda)$ to
$$\=F(\lambda)=\mtxi{F(\lambda) \cr {1\over 4}\vec e \zlo n+1 \cr}mtxi/,$$
a square $n+1$ by $n+1$ upper triangular matrix.
Using the Triangle Inequality, we have that
$$
\norm{\=F(\lambda )}\zlo 2 ≤ {1\over 4} + \!
\left(\norm{A}\zlo 2 + \norm{B}\zlo 2 \right) + \!
\abs{\lambda } ≤ 1,
$$
for any $\lambda $ satisfying $(\lambda bound)$.
Let us pick a particular value for $\lambda $ satisfying $(\lambda bound)$,
and let
$G=\=F(\lambda )$.
Observe that
$$ \mthop det (G)=\abs{b\zlo 1 a\zlo 2,1 \ldotss a\zlo n,n-1 {1\over 4}} > \epsilon .$$
Consider the S.V.D. of $G=U\Sigma V\trp $. Then
$$
\epsilon < \abs{\mthop det (G)} \!
= \abs{\mthop det (U)\mthop det (\Sigma)\mthop det (V\trp)} \!
= \abs{\mthop det (\Sigma)},
$$
since for unitary matrices, the determinant has absolute value $1$.
If we assume that the singular values are ordered, then we can write
$$1 ≥ \norm{G}\zlo 2 = \sigma\zlo 1 ≥ \ldotss ≥ \sigma\zlo n+1 ≥ 0.$$
Since
$\sigma\zlo 1 \ldotss \sigma\zlo n ≤ 1$,
it follows that
$$
\epsilon < \abs{\mthop det (\Sigma)} = \!
(\sigma\zlo 1 \ldotss \sigma\zlo n ) \sigma\zlo n+1 ≤ \sigma\zlo n+1
$$
Thus, for any $\lambda $ satisfying $(\lambda bound)$,
there is no $\epsilon $-perturbation of
$G=\=F(\lambda )$ that will make it singular.
In order to show that any $\epsilon $-perturbation of $A$, $B$
is completely controllable, we
must show that the resulting perturbed $\s F(\s \lambda )$
corresponding to $\=F(\lambda )$,
using a perturbed
eigenvalue $\s \lambda $, is still non-singular. But any such eigenvalue
$\s \lambda $ still satisfies $(\lambda bound)$, and any such perturbed
$\s F(\s \lambda )$
is not more than an $\epsilon $-perturbation of $\=F(\s \lambda )$
coming from
the original $A$, $B$. Hence $\s F(\s \lambda )$ cannot be singular.
\QED
Following the conjecture given before the theorem, we can define our sensitivity
to be the product $\mu\zlo s $ of the smallest singular values of the
sub-diagonal blocks in $(D.5a)$.
Note that, although this bound is robust, it has severe limitations. For
one, it is a function of the determinant of the augmented matrix $\=F$ and
hence can be very sensitive to perturbations in the data.
The following example is a case in point
$$
\mtxi{\dot x\zlo 1 \cr \vtskip
\dot x\zlo 2 \cr}mtxi/
=
\mtxii{-{1\over 2} ⊗ 0 \cr \vtskip
-\sqrt{\epsilon} ⊗ -{1\over 2} \cr}mtxii/
\mtxi{x\zlo 1 \cr \vtskip
x\zlo 2 \cr}mtxi/
+
\mtxi{\sqrt{\epsilon} \cr \vtskip
0 \cr}mtxi/
u.
$$
It is shown below that though the product of the subdiagonal
elements is small (equal to $\epsilon$), there does not exist an
$\epsilon$-perturb\-ation to this system with a controllable part of
dimension $1$.
Furthermore, in the multiple input case, the bound
is only a heuristic, but one which
seems to work as well as in the single input case.
It will be seen in Chapter 4 that this measure can be, and very often
is, extremely pessimistic.
We now prove the assertion concerning the above example.
}
{\let\spcol=\quad \parhead{Proposition.}
\thbody{If $\epsilon < .04$ then no $\epsilon$-perturbation of the system
$\dot\vx=A\vx+B\vu$ with
$$
A=
\mtxii{-{1\over 2} ⊗ 0 \cr \vtskip
-\sqrt{\epsilon} ⊗ -{1\over 2} \cr}mtxii/
\hbox{\quad and \quad}
B=
\mtxi{\sqrt{\epsilon} \cr \vtskip
0 \cr}mtxi/.
$$
has a controllable part of dimension 1.}thbody/
\parhead{Proof:}
We consider what happens if we apply a small
perturbation $E$ to $A$ and $F$ to $B$,
where we denote
$$
E=
\mtxii{\zeta↓1 ⊗ \zeta↓2 \cr \vtskip
\zeta↓3 ⊗ \zeta↓4 \cr}mtxii/
\hbox{\quad and \quad}
F=
\mtxi{\zeta↓5 \cr \vtskip
\zeta↓6 \cr}mtxi/,
$$
and the elements of $E$ and $F$ satisfy
$\abs{\zeta↓i}≤{\sqrt{\epsilon}\over 3}$, $i=1,\ldotss,6$.
We will show that under any such perturbation,
the controllable space $\Sscr↓c$ will have dimension $2$.
The rank of $B+F$ is $1$ for any such $F$
so we may construct an orthogonal rotation so that
$$
\mtxii{ c ⊗ s \cr -s ⊗ c \cr}mtxii/
(B+F)
=
\mtxi{ z \cr 0 \cr}mtxi/,
\eqno (rotate)
$$
for some $z \not= 0$.
This yields the relations
$$
\eqalgn{
c(\sqrt{\epsilon} + \zeta↓5) + s \zeta↓6 ⊗= z \cr \vtskip
- s (\sqrt{\epsilon} + \zeta↓5) + c \zeta↓6 ⊗= 0, \cr
}eqalgn/
$$
from which it follows that $c \not= 0$ and
$$
{s\over c} = {-\zeta↓6 \over \sqrt{\epsilon} + \zeta↓5} .
$$
Hence
$$
\abs{s\over c} ≤ {1\over 2}.
$$
Since we have an orthogonal rotation, we may use $s↑2+c↑2=1$ to obtain
a bound on c:
$$
c↑2 ≥ {4\over 5} .
$$
We apply the rotation used in $(rotate)$ to $A$ to get
$$
\mtxii{ c ⊗ s \cr -s ⊗ c \cr}mtxii/
(A+E)
\mtxii{ c ⊗ -s \cr s ⊗ c \cr}mtxii/
=
\mtxii{ x ⊗ x \cr -y ⊗ x \cr}mtxii/.
$$
In order to show $\mthop dim \Sscr↓c = 2$, it suffices to show that
$\abs{y}>\epsilon$.
But from the last equation, we have the following expression for $y$:
$$
\eqalgn{
y
⊗=
c↑2 (-\sqrt{\epsilon} + \zeta↓3) - s↑2\zeta↓2 +
c s (\zeta↓4 - \zeta↓1)
\cr \vtskipp
⊗=
c↑2 \left(-\sqrt{\epsilon} + \zeta↓3 - {s\over c}↑2\zeta↓2 +
{s\over c} (\zeta↓4 - \zeta↓1) \right)
\cr
}eqalgn/
$$
Thus we obtain the following estimate for $\abs{y}$:
$$
\eqalgn{
\abs{y}
⊗\ ≥\
c↑2 \left({2\over 3}\sqrt{\epsilon} -
{1\over 12}\sqrt{\epsilon} -
{1\over 3}\sqrt{\epsilon}\right)
\cr
\vtskipp
⊗\ ≥\
{1\over 4} c↑2 \sqrt{\epsilon} \ ≥\ {1\over 5} \sqrt{\epsilon}
\ >\ \epsilon .
\cr
}eqalgn/
$$
Hence we may conclude that we would have to perturb the system by at least order
$\sqrt{\epsilon}$ in order to achieve a controllable space of
dimension $1$.
\QED
}
\pagebreak
{\let\spcol=\quad \donothing{We include here another analysis of the Staircase Algorithm.
Suppose we have a decomposition like
$$
\eqalgn{
\mtxi{\dot\vx↓1 \cr \dot\vx↓2 \cr}mtxi/
⊗=
\mtxii{A↓{11} ⊗ A↓{12} \cr 0 ⊗ A↓{22} \cr}mtxii/
\mtxi{\vx↓1 \cr \vx↓2 \cr}mtxi/
+
\mtxi{B↓1 \cr 0 \cr}mtxi/
\vu
\cr
}eqalgn/
$$
which results from a relative perturbation of order $\eta$ from the original system,
then (from theorem 4.11 of [Stewart 1970b]) the invariant subspace $Q\zlo c $
could be perturbed by as much as $\norm{P}={2\eta\over \delta}$.
If $\delta$ is small, indicating a badly conditioned problem, and $A$ is perturbed
by only $\epsilon$, then $X$, by this analysis, could be perturbed by as
much as
$$
\Delta X\zlo final \approx {2\epsilon \over \delta}.
$$
If $X$ contained the vectors $B$, then $X+\Delta X$ probably does not to within
an error of $\norm{\Delta X}$, and one would need a presumably larger space
to re-grasp $B$.
Another analysis based on the actual operations is next presented.
The reduction is performed by applying a series of orthogonal transformations.
Suppose at a certain step the transformation $X$ is perturbed by $F$, such that
$\norm{F}=\epsilon≤1$. Then we have the following expression:
$$
\eqalgn{
(X+F)A(X+F)\inv ⊗= A+XAG+FAX\inv+FAG \cr
⊗= A + \Delta A + O(\epsilon\zhi 2 ),\cr
}eqalgn/
$$
where we approximate $(X+F)\inv\approx (X\inv+G)$, $\norm{G}\approx \epsilon$,
and also $\norm{\Delta A}\approx 2\epsilon$. Each application of an $X$ perturbed by
$F$ alters $A$ by about $2\epsilon$. The new transformation $X$ computed in the
next step will also be altered by a similar amount since it is based on the
elements in the matrix $A$, which is double the perturbation in the previous step.
After $k$ steps the perturbation will be
$$
\Delta X\zlo final \approx 2\zhi k n \epsilon
$$
where $n$ is the order of the matrix $A$, and $\epsilon$ in the initial
perturbation.
}donothing/
}
{\let\spcol=\quad For the $4$ by $4$
example $(sample)$, the computed measure is
$$\mu\zlo s = 7.44\times 10\zhi -3 ,$$
and for the $11$ by $11$ example, it is
$$\mu\zlo s = 5.05\times 10\zhi -4 .$$
In these examples, it was necessary to scale the matrices to be of norm unity
in order to satisfy the requirements for the Theorem.
}
\newpage